package com.tys.algorithm.advanced.test.class16;

import com.tys.algorithm.advanced.code.class16.Node;

import java.util.HashSet;
import java.util.Stack;

public class Code02_DFS {
    //深度优先遍历：迭代版
    public static void dfs(Node node) {
        if (node == null) {
            return;
        }
        //栈：放整条路径
        Stack<Node> stack = new Stack<>();
        //set
        HashSet<Node> set = new HashSet<>();
        //将node压栈
        stack.add(node);
        //node放入set
        set.add(node);
        //打印值
        System.out.println(node.value);
        //栈为空退出循环
        while (!stack.isEmpty()) {
            //栈中弹出节点：入栈时已经打印
            Node cur = stack.pop();
            //遍历邻居
            for (Node next : cur.nexts) {
                if (!set.contains(next)) { //邻居没被登记
                    stack.push(cur); //当前节点压回栈
                    stack.push(next); //邻居压栈
                    set.add(next); //登记到set
                    System.out.println(next.value); //打印邻居
                    break; //不继续遍历
                }
            }
        }
    }


}
